Abstract: This work revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the "reconstruction paradigm" in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and Tell (STOC 2024) showed that both of these tools can be derandomized in the specific context of read-once branching programs (ROBPs), but left open the question of derandomizing them in more general settings.
Our main contributions give appealing evidence that derandomization of the two tools is possible in general settings, show surprisingly strong consequences of such derandomization, and reveal several new settings where such derandomization is unconditionally possible for algorithms stronger than ROBPs (with useful consequences). In particular, we prove that deterministically solving the search problem of producing a transformation from distinguishers to next-bit predictors (i.e. derandomizing Yao's lemma) if equivalent to generic derandomization prBPP = prP.
This is a joint work with Edward Pyne (MIT) and Roei Tell (University of Toronto) to appear in FOCS 2024. Full version of the paper: ECCC - TR24-139 (weizmann.ac.il).